#include <iostream>
#include <cassert>
#include <vector>

using namespace std;

// 209. Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/description/
//
// 滑动窗口的思路
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution
{
public:
    int minSubArrayLen(int target, vector<int> &nums)
    {
        assert(target > 0);

        int l = 0, r = -1; // nums[l...r]为我们的窗口，r初始为-1，表示一个不存在的窗口
        int sum = 0;
        int res = nums.size() + 1;

        while (l < nums.size()) // 窗口左边界还在数组范围内，滑动继续
        {
            if (r + 1 < nums.size() && sum < target)
            {
                // sum += nums[++r];
                r++;
                sum += nums[r];
            }
            else // r已经到头，或者sum>=s，此时移动左指针
            {
                // sum -= nums[l++]
                sum -= nums[l]; // 把最左侧的值减掉
                l++;
            }

            if (sum >= target)
                res = min(res, r - l + 1);
        }

        // 说明没有找到结果
        if (res == nums.size() + 1)
            return 0;

        return res;
    }
};

int main()
{
    int nums[] = {2, 3, 1, 2, 4, 3};
    vector<int> vec = vector<int>(nums, nums + sizeof(nums) / sizeof(int));
    int s = 7;

    int res = Solution().minSubArrayLen(s, vec);
    cout << res << endl;

    return 0;
}